In digital communication systems, a low density parity-check code (LDPC) is an error correcting code used in noisy communication channels to reduce a probability of a loss of information. LDPC codes are generally represented using a bipartite graph and decoded by an iterative message-passing (MP) algorithm. The MP algorithm iteratively passes messages between variable nodes (e.g., message nodes) and check nodes (e.g., constraint nodes) along connected edges of the bipartite graph. If the messages passed along the edges are probabilities, then the decoding is referred to as belief propagation (BP) decoding.
Compressive sensing (CS), which can be based on a low-density measurement matrix, may also be used for error correction coding. CS is a signal processing technique for reconstructing a signal that takes advantage of a signal's sparseness or compressibility. Using CS, an n-dimensional signal having a sparse or compressible representation can be reconstructed from m linear measurements, even if m<n. As with LDPC, a compressive sensing (CS) system can use belief propagation (BP) decoding. Such a system is referred to herein as a CS-BP system.
The complexity of CS-BP decoding is much higher than LDPC decoding because the constraint nodes of a CS-BP system have to compute convolutions of several probability distribution functions (PDFs). A CS-BP system computes measurements via weighted sum operations, instead of logical exclusive OR (XOR), as used for binary LDPC systems.
A standard processing solution for CS-BP systems is to perform processing in the frequency domain, such as via fast Fourier transform (FFT) and inverse FFT (IFFT). This frequency domain based processing converts convolution to multiplication and deconvolution to division. However, such processing is not efficient for binary-input PDFs.